package 剑指offer;

public class 剑指offer26重排链表 {

    public static void main(String[] args) {
        ListNode node4 = new ListNode(3,null);
        ListNode node3 = new ListNode(4,node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(5,node2);
        剑指offer26重排链表 o = new 剑指offer26重排链表();
        o.reorderList(node1);
    }

    public void reorderList(ListNode head) {
        //快慢指针寻找中点
        if (head == null || head.next == null){
            return;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //此时找到中间节点。反转后一半链表
        ListNode last = slow;
        slow.next = null;
        ListNode lastNewNode = reverceList(last);
        //拼接链表，创建虚拟节点
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while (lastNewNode != null){
            cur.next = head;
            head = head.next;
            cur = cur.next;

            cur.next = lastNewNode;
            lastNewNode = lastNewNode.next;
            cur = cur.next;
        }
        cur.next = head == null ? null : head;
    }
    public ListNode reverceList(ListNode head){
        if (head == null || head.next == null){
            return head;
        }
        ListNode next = head.next;
        ListNode newNode = reverceList(head.next);
        next.next = head;
        head.next = null;
        return newNode;
    }
}
